package cn.edu.xjtu.work.isSubtree;

import java.util.LinkedList;
import java.util.Queue;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 572. 另一棵树的子树
 * 
 * 
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true
 * ；否则，返回 false 。
 * 
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(4);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.right.left = new TreeNode(2);

        TreeNode subRoot = new TreeNode(3);
        subRoot.left = new TreeNode(1);
        subRoot.right = new TreeNode(2);

        Solution solu = new Solution();
        System.out.println(solu.isSubtree(root, subRoot));
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode temp = q.poll();
            if (temp.left != null) {
                q.add(temp.left);
            }
            if (temp.right != null) {
                q.add(temp.right);
            }

            if (temp.val == subRoot.val) {
                if (isSame(temp, subRoot)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        if (root.val == subRoot.val) {
            return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
        } else {
            return false;
        }
    }
}
